import java.util.Stack;

public class BST<E extends Comparable<E>>{
    /**
     * Node
     */
    public class Node {
        public E e;
        public Node left,right;
        public Node(E e){
            this.e=e;
            this.left=null;
            this.right=null;
        }
        
    }
    private Node root;
    private int size;
    BST(){
        this.root=null;
        this.size=0;
    }
    public int size(){
        return size;
    }
    public boolean isEmpty(){
        return this.size()==0;
    }
    public void add(E e){
        if(root==null){
            root= new Node(e);
            size++;
        }else{

        }
    }
    private Node add(Node node,E e){
        if(node==null){
            size++;
            return new Node(e);
        }
        if(e.compareTo(node.e)<0){
          node.left=add(node.left,e);
        }
        if(e.compareTo(node.e)>0){
           node.right=add(node.right,e);
        }
        return node;
    }
    private boolean contains(E e){
    return    contains(root,e);
    }
    private boolean contains(Node node,E e){
        if(e.compareTo(node.e)<0){
           return contains(node.left,e);
        }
        if(e.compareTo(node.e)>0){
           return contains(node.right,e);
        }
        return true;
    }
    public void traverse(){

    }
    public void preOrder(Node node){
        if(node==null){
            return;
        }
        System.out.println(node.e);
        preOrder(node.left);
        preOrder(node.right);
 
    }
    public void midOrder(Node node){
        if (node==null) {
            return;
        }
        midOrder(node.left);
        System.out.println(node.e);
        midOrder(node.right);
    }
    public void afterOrder(Node node) {
        if (node==null) {
            return;
        }
        afterOrder(node.left);
        afterOrder(node.right);
        System.out.println(node.e);
    }
    public void floorOrder(Node root){
        Stack<Node>nodeStack=new Stack<Node>();
        if (root==null) {
            return;
        }
        nodeStack.push(root);
        while (!nodeStack.isEmpty()) {
            Node cur=nodeStack.pop();
            nodeStack.push(cur.left);
            nodeStack.push(cur.right);
            System.out.println(cur.e);
        }
    }


     //      10
        //    5    15
        //3     6 11    22
        //10 5
    public void midOrderNR(Node root){
        if(root==null){
            return;
        }
        Stack<Node>nodeStack=new Stack<Node>();
        nodeStack.push(root);
        while(!nodeStack.isEmpty()){
            Node cur=nodeStack.pop();
            if(cur.right!=null){
                nodeStack.push(cur.right);
            }
            System.out.println(cur.e);
            if(cur.left!=null){
                nodeStack.push(cur.left);
            }
        }


    }
    public void preOrderNR(Node node){
        if (node==null) {
           return;
        }
   
        Stack<Node>nodeStack=new Stack<Node>();
        nodeStack.push(node);
        while (!nodeStack.isEmpty()) {
            Node cur=nodeStack.pop();
            System.out.println(cur.e);
            nodeStack.push(cur.right);
            nodeStack.push(cur.left);
        }
        
    }

}